package leetcode.lt100;

import java.util.ArrayList;
import java.util.List;

class Solution_68 {

	public static void main(String[] args) {

		String[] words = { "This", "is", "an", "example", "of", "text", "justification." };
		new Solution_68().fullJustify(words, 16);
	}

	public List<String> fullJustify(String[] words, int maxWidth) {
		List<String> res = new ArrayList<>();
		int l = words.length;
		// 逐行递归遍历
		add(res, words, maxWidth, 0, l);
		return res;
	}

	private void add(List<String> res, String[] words, int maxWidth, int start, int l) {
		int end = start;
		int nowL = 0;
		while (end != l && nowL + words[end].length() + end - start <= maxWidth) {
			nowL += words[end].length();
			end++;
		}
		end--;
		if (end == l - 1) {
			StringBuffer sb = new StringBuffer();
			for (int i = start; i < end; i++) {
				sb.append(words[i]);
				sb.append(" ");
			}
			sb.append(words[end]);
			int ltmp = sb.toString().length();
			for (int i = ltmp; i < maxWidth; i++) {
				sb.append(" ");
			}
			res.add(sb.toString());
			return;
		}
		if (end == start) {
			StringBuffer sb = new StringBuffer();
			sb.append(words[start]);
			for (int i = words[start].length(); i < maxWidth; i++) {
				sb.append(" ");
			}
			res.add(sb.toString());
			add(res, words, maxWidth, end + 1, l);
		} else {
			StringBuffer sb = new StringBuffer();
			int arg = (maxWidth - nowL) / (end - start);
			int mod = (maxWidth - nowL) % (end - start);
			StringBuffer sbtmp = new StringBuffer();
			for (int i = 0; i < arg; i++) {
				sbtmp.append(" ");
			}
			String stmp = sbtmp.toString().intern();

			for (int i = start; i < end; i++) {
				sb.append(words[i]);
				sb.append(stmp);
				if (i - start < mod)
					sb.append(" ");
			}
			sb.append(words[end]);
			res.add(sb.toString());
			add(res, words, maxWidth, end + 1, l);
		}
	}

}